#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxd = 12+2;
int A[maxd];
ll d[maxd][120][120][120];
ll l, r;

ll dp(int pos, int x, int mod, int sum, bool flg){
    if(pos == 0) return (x==sum && mod==0);
    if(flg && d[pos][x][mod][sum]!=-1) return d[pos][x][mod][sum];
    int m = flg?9:A[pos];
    ll ans = 0;
    for (int i = 0; i <= m; ++i) {
        ans += dp(pos-1, x, (mod*10+i)%x, sum + i, flg||i<m);
    }
    if(flg) d[pos][x][mod][sum] = ans;
    return ans;
}

ll cal(ll x){
    if(x==0) return 0;
    int pos = 0;
    do{
        A[++pos]=x%10;
        x/=10;
    }while(x);
    ll ans = 0;
    for (int i = 1; i <= 9*12; ++i) {
        ans += dp(pos, i, 0, 0, false);
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);

    memset(d, -1, sizeof(d));
    int T; cin >> T;
    for (int i = 1; i <= T; ++i) {
        cin >>r;
        cout << "Case " << i << ": " << cal(r)<< endl;
    }

    return 0;
}